In packet-switched networks, a router is a device or, in some cases, software in a computer, that determines the next network point to which a data packet should be forwarded toward its destination. The router is typically coupled to at least two routers and decides which way to send each data packet based on its current understanding of the state of the network to which it is connected. A router may create or maintain a table (hereinafter a “routing table”) of the available routes and their conditions and use this information along with distance and cost algorithms to determine the best route for a given data packet. Typically, a data packet may travel through a number of routers before arriving at its destination. Routing is a function associated with the network layer (i.e., layer 3) in the standard model of network programming, the Open Systems Interconnection (OSI) model.
Unicast, broadcast, and multicast are three well known techniques for transmitting data packets (e.g., audio and video data packets) from a source (e.g., a server) to one or more receivers (e.g., a desktop computer system) via packet-switched networks. Unicast is a point-to-point communication technique in which data packets are transmitted between a single source and a single receiver. Broadcast communication enables one source to transmit data packets to all receivers in a broadcast domain. Multicasting allows a source or several sources to transmit data packets simultaneously to select receivers, i.e., those receivers in a multicast group. During multicast transmission, multicast data packets are replicated by multicast enabled routers at the point where communication paths diverge to separate receivers of a multicast group. In this fashion, the multicast protocol delivers data to multiple receivers without burdening the source or consuming excessive network bandwidth.
There are several different multicast protocols, including but limited to Sparse Mode (SM) and Source Specific Mode (SSM). The SM protocol may be defined in Internet Engineering Task Force (IETF) Request For Comments (RFC) 2362 entitled “Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification,” published in June 1998, and hereby incorporated by reference in its entirety, or in revisions thereof. The SSM protocol may be defined RFC 3569 entitled “An Overview of Source-Specific Multicast (SSM),” published in July 2003, and hereby incorporated by reference in its entirety, or in revisions thereof.
FIG. 1 illustrates relevant components of a packet-switched network 10 that can employ either SM or SSM protocols. More particularly, FIG. 1 shows sources 12 coupled to receivers 14 (or potential receivers) via a series of routers 16 and data communication links 20. In SM networks, the various multicast enabled routers establish a default multicast distribution tree, referred to as a “shared tree,” for each multicast group. The shared tree is rooted at a rendezvous point (RP) router that acts as the distribution point for multicast data transmitted to receivers of a multicast group. Before a source can begin transmitting data to receivers of a multicast group, the RP router must discover or learn about that source. The RP router learns of the source when the source first registers with the RP router. Moreover, for a receiver to join a multicast group, the receiver must join towards the RP router. Once a receiver joins a multicast group, the RP router establishes a communication path between one or more sources and the newly joined receiver.
To further illustrate, presume that router 16d is configured in network 10 as the RP router for a multicast group G1 consisting of receivers 14a and 14b. Further, presume that device 14c seeks to join multicast group G1 as a receiver. Device 14c can join the multicast group by first generating a membership report in compliance with Internet Management Group Protocol version 1 (IGMPv1) or Internet Management Group Protocol version 2 (IGMPv2). The address G1 of the multicast group is included in the membership report along with the address (e.g., an Internet address) of device 14c. It is noted that IGMP is the terminology used in IPv4. In IPv6, IGMP is referred to as Multicast Listener Discovery (MLD). Thus, MLDv1 is the same as IGMPv2 and MLDv2 is the same as IGMPv3.
The IGMP membership report is transmitted by device 14c to edge router 16h via data communication link 20k. Edge router 16h, in response to receiving the IGMP report from device 14c, generates a request to join multicast group G1. In SM networks, this request is designated PIM (*, G1) JOIN, and its sent hop by hop towards RP router 16d. The “*” within the request indicates that the device (e.g., device 14c) seeking to join multicast group G1 should receive data from all sources providing data to the multicast group G1. Thus, if sources 12a and 12b are providing data to receivers within the multicast group G1, device 14c will receive data from both sources 12a and 12b once device 14c joins multicast group G1 as a receiver. For purposes of explanation, it will be presumed that device 12a is the only source providing data to multicast group G1.
The PIM (*, G1) JOIN is transmitted by edge router 16h to RP router 16d. RP router 16d, in response to receiving PIM (*, G1) JOIN, accesses at table to learn the identity (e.g., addresses) of sources transmitting data to multicast group G1. Once the source identities are known, RP router 16d creates a communication path between the sources and device 14c. For purposes of explanation, it will be presumed that the table in RP router 16d indicates that only source 12a is transmitting data to multicast group G1. Accordingly, RP router 16d creates a communication path between source 12a and device 14c that includes RP router 16d. Device 14c receives data packets from source 12 once this communication path is established.
After the communication path is established between source device 12a and receiver 14c, edge router 16h may trigger a routine to create a faster and/or more efficient communication path between source 12a and receiver 14c that may not include RP router 16d. The new and more efficient communication path between source 12a and receiver 14c is often referred to as a source specific multicast tree. Once the new and more efficient communication path is established, the original communication path though RP router 16d is pruned away. Unfortunately, the creation of a new and more efficient source specific multicast tree and the subsequent pruning of the original communication path, adds complexity to the overall operation of network 10.
As noted above, network 10 may also operate according to the SSM protocol. Unlike an SM network, an SSM network does not employ an RP router. In SSM protocol networks, when a device seeks to join a multicast group as a receiver, the device will know in advance the identity of the source or sources from which it seeks to receive multicast data. This enables a new receiver to directly join a multicast group on the shortest path tree towards the source or sources (i.e., without first going through an RP router). When more than one source is transmitting data packets to a multicast group, SSM networks enable multicast group receivers to select one or more the sources from which to receive data. Compared to the SM protocol, the SSM protocol is more efficient.
To illustrate operational aspects of SSM protocol, presume that network 10 operates according to the SSM protocol, and that devices 14a and 14b are receiver members of a multicast group G2 that receive data from source 12a. Further, presume that device 14c seeks to join multicast group G2 as a new receiver. Typically, before device 14c can join multicast group G2, device 14b must generate a membership report using IGMP version 3 (IGMPv3) protocol. It is noted that device 14c can join multicast group G2 as a receiver even though device 14c executes only IGMPv1 or IGMPv2 if device 14c and/or edge router 16h implement the method described in U.S. patent application Ser. No. 10/208,977 entitled “Source Specific Multicast Group to Source Mapping,” filed on Jul. 31, 2002. The foregoing patent application is incorporated herein by reference in its entirety. However, for purposes of explanation, it will be presumed that device 14c operates according to IGMPv3 only.
The IGMPv3 membership report identifies both the source device 12a and the multicast group that device 14c wishes to join. In contrast, the IGMPv1 or IGMPv2 membership report generated for the SM protocol does not identify the source from which data is sought. The IGMPv3 report generated by device 14c is transmitted to edge router 16h. Thereafter edge router 16h establishes a fast and efficient communication path between source device 12a and device 14c which does not include router 16d, but which may include routers 16a, 16b, 16f, 16g, and 16h. With this communication path established, source device 12a transmits data to receiver device 14c while also transmitting data to the other receivers in multicast group G2.
As noted, traditional SM networks require an RP router for source discovery. However, for some SM networks, the existence of an RP router is not desired. A mobile network in which routers are mobile and in data communication with each other via wireless communication network, is one example where the existence of an RP router is not desired. One reason an RP routers is not desired in a mobile network is that it is not known in advance which routers in the network will be active. In order to guarantee operation in a mobile network that employs SM protocol, each router must be able to operate as an RP router. This may also lead to the added difficulty that it is not known which router will act as the active RP at a given point in time. This causes operational problems in the field, since network operators want the network to be predictable. Accordingly, a need exists for an invention that enables communication in an SM network that lacks an RP router.
The use of the same reference symbols in different drawings indicates similar or identical items.